package sorting;

import java.util.List;
import java.util.ArrayList;

public class Sorting implements SortingInterface{

	// BUBBLESORT
	public int[] bubbleSort(int[] array) {
		int ultimoTermo = array.length - 1;

		while ( 0 < ultimoTermo ) {

			for ( int i = 0; i < ultimoTermo; i++ ) {
				if (array[i] > array[i+1]) {
					array = swap(array, i+1, i);
				}

			}
			ultimoTermo --;
		}
		return array;
	}

	// BUBBLESORT BIDIRECIONAL
	public int[] bidirectionalBubbleSort(int[] array) {
		int ultimoTermo = array.length - 1;
		int primeiroTermo = 0;

		while ( primeiroTermo < ultimoTermo ) {

			for ( int i = primeiroTermo; i < ultimoTermo; i++ ) {
				if (array[i] > array[i+1]) {
					array = swap(array, i+1, i);
				}
			}

			ultimoTermo --;

			for ( int j = ultimoTermo; j >= primeiroTermo+1; --j) {
				if (array[j] < array[j-1]) {
					array = swap(array, j, j-1);
				}
			}

			primeiroTermo ++;
		}
		return array;
	}

	
	// BUBBLESORT BIDIRECIONAL 2
	public int[] bidirectionalBubbleSort2(int[] array) {
		int ultimoTermo = array.length - 1;
		int primeiroTermo = 0;

		while ( primeiroTermo < ultimoTermo ) {
			int j = ultimoTermo;

			for ( int i = primeiroTermo; i < ultimoTermo && j >= primeiroTermo+1; i++ ) {

				if (array[i] > array[i+1]) {
					array = swap(array, i+1, i);
				}

				if (array[j] < array[j-1]) {
					array = swap(array, j, j-1);
				}
				--j;

			}

			ultimoTermo --;
			primeiroTermo ++;
		}
		return array;
	}

	private int[] swap(int[] array, int menor, int maior){
		int temporario = array[maior];
		array[maior] = array[menor];
		array[menor] = temporario;

		return array;
	}

	
	// MERGESORT
	public int[] mergeSort(int[] array) {

		if (array.length == 1){
			return array;
		} else {
			int[] A = mergeSort(divide(array, true));
			int[] B = mergeSort(divide(array, false));
			int[] resultado = intercala(A, B);
			return resultado;
		}
	}

	private int[] intercala (int[] array1, int[] array2 ){
		int contadorArray1 = 0;
		int contadorArray2 = 0;
		int contadorArray = 0;
		int tamanhoDoArray = array1.length + array2.length;

		int[] arrayResultado = new int[tamanhoDoArray];


		while ( contadorArray1 < array1.length && contadorArray2 < array2.length ){

			if (array1[contadorArray1] < array2[contadorArray2]) {
				arrayResultado[contadorArray] = array1[contadorArray1];
				contadorArray1 ++;
			} else {
				arrayResultado[contadorArray] = array2[contadorArray2];
				contadorArray2 ++;
			}

			contadorArray ++;

		}

		if (contadorArray1 != array1.length ) {
			for ( int i = contadorArray1; i < array1.length; i++){
				arrayResultado[contadorArray] = array1[i];
				contadorArray ++;
			}
		}

		if (contadorArray2 != array2.length ) {
			for ( int i = contadorArray2; i < array2.length; i++){
				arrayResultado[contadorArray] = array2[i];
				contadorArray ++;
			}
		}

		return arrayResultado;
	}


	private int[] divide(int[] array, boolean ehComeco){
		int[] cabeca;
		int[] calda;


		if (array.length%2 == 0){
			cabeca = new int[array.length/2];
			calda = new int[array.length/2];

		} else {
			cabeca = new int[(array.length+1)/2];
			calda = new int[array.length/2];

		}

		int cont1 = 0;
		int cont2 = 0;
		for (int i = 0; i < array.length; i++){
			if (i < cabeca.length ){
				cabeca[cont1] = array[i];
				cont1 ++;
			} else {
				calda[cont2] = array[i];
				cont2 ++;
			}			
		}

		if (ehComeco) {
			return cabeca;
		}

		return calda;
	}

	
	// COUNTINGSORT
	public int[] countingSort(int[] array) {
		int maiorNumero = Integer.MIN_VALUE;
		
		for (int i = 0; i < array.length; i++){
			if (array[i] > maiorNumero){
				maiorNumero = array[i];
			}
		}
		
		int[] arrayC = new int[maiorNumero+1];
		int[] arrayB = new int[array.length];
		
		for (int i = 0; i < arrayC.length; i++){
			arrayC[i] = 0;
		}
		
		for (int i = 0; i < array.length; i++ ){
			arrayC[array[i]] = arrayC[array[i]] + 1;
		}
		
		for (int i = 1; i < arrayC.length; i++ ){
			arrayC[i] = arrayC[i] + arrayC[i - 1];
		}
		
		for (int i = 0; i < array.length; i++ ){
			arrayC[array[i]] = arrayC[array[i]] - 1;
			arrayB[arrayC[array[i]]] = array[i];
		}
		
		return arrayB;
	}
	
	
	// SELECTIONSORT
	public int[] selectionSort(int[] array){
		int primeiraPossicao = 0;
		
		while (primeiraPossicao < array.length - 1){
			int menorElemento = array[primeiraPossicao];
			int possicaoMenorElemento = primeiraPossicao;
			
			for ( int i = primeiraPossicao; i < array.length; i++){
				if (menorElemento > array[i]){
					menorElemento = array[i];
					possicaoMenorElemento = i;
				}
			}
			array = swap(array, primeiraPossicao, possicaoMenorElemento);
			primeiraPossicao ++;
		}
		return array;
	}
	
	
	// BUCKETSORT
	@SuppressWarnings({ "unchecked", "rawtypes" })
	public int[] bucketSort(int[] array){
		int maiorNumero = Integer.MIN_VALUE;
		
		for (int i = 0; i < array.length; i++){
			if (array[i] > maiorNumero){
				maiorNumero = array[i];
			}
		}
		
		int n = array.length;
		
		List[] bucket = new ArrayList[(maiorNumero/10)+1];
		
		for (int i = 0; i < bucket.length; i++){
			bucket[i] = new ArrayList();
		}
		
		for (int i = 0; i < n; i++){
			bucket[array[i]/10].add(array[i]);
		}
		
		int[][] arrays = transformaArray(bucket);

		for (int i = 0; i < arrays.length; i++){
			arrays[i] = selectionSort(arrays[i]);
		}
		return concatenaArrays(arrays, n);
		
	}
	
	private int[][] transformaArray(@SuppressWarnings("rawtypes") List[] bucket){
		int[][] arrays = new int[bucket.length][];
		
		for (int i = 0; i < bucket.length; i++){
			arrays[i] = new int[bucket[i].size()];
		}
		
		for (int i = 0; i < bucket.length; i++){
			for (int j = 0; j < bucket[i].size(); j++){
				arrays[i][j] = (Integer) bucket[i].get(j);
			}
		}
		return arrays;
	}
	
	private int[] concatenaArrays(int[][] array, int tamanho) {
		int[] retorno = new int[tamanho];
		int cont = 0;
		
		for (int i = 0; i < array.length; i++){
			for (int j = 0; j < array[i].length; j++){
				retorno[cont] = array[i][j];
				cont ++;
			}
		}
		return retorno;
		
	}

	
	// INSERTION SORT
	public int[] insertionSort(int[] array){
		
		int finalDaLista = 0;
		
		while (finalDaLista < array.length-1 ) {
			int proximoElemento = array [finalDaLista + 1];
			int indiceDoProximoElemento = finalDaLista + 1;
			for (int i = finalDaLista ; i >= 0; i--){
				if (proximoElemento < array[i]){
					array = swap(array, indiceDoProximoElemento, i);
					indiceDoProximoElemento --;
				}
				else {
					break;
				}
			}
			finalDaLista ++;
			
		}
		return array;
	}
	
	
	// QUICKSORT
	public int[] quickSort(int[] array, int comecoDoArray, int fimDoArray){
		
		if (comecoDoArray >= fimDoArray){
			return array;
		}
		
		int indiceDoPivo = particion(array, comecoDoArray, fimDoArray);
		quickSort(array, comecoDoArray, indiceDoPivo-1);
		quickSort(array, indiceDoPivo+1, fimDoArray);
		return array;
	}
	
	private int particion(int[] array, int comecoDoArray, int fimDoArray){
		int i = comecoDoArray + 1;
		int j = fimDoArray; 
		int p = array[comecoDoArray];
		
		while (i <= j){
			if (array[i] <= p){
				i++;
			} else if (array[j] > p){
				j --;
			} else {
				array = swap(array, i, j);
			}
		}
		
		array = swap(array, comecoDoArray, i-1);
		return i-1;
	}
		
	private int[] concatenaArray(int[] arrayComeco, int[] arrayFim){
		int[] resultado = new int[arrayComeco.length + arrayFim.length];
		
		int indiceResultado = 0;
		while (indiceResultado < resultado.length){
			if (arrayComeco.length > indiceResultado){
				resultado[indiceResultado] = arrayComeco[indiceResultado];
			} else {
				resultado[indiceResultado] = arrayFim[indiceResultado - arrayComeco.length];
			}
			indiceResultado ++;
		}
		return resultado;
	}
	
	
	private void calculoDaMediana3(int[] array, int esquerda, int direita){
		int centro = (esquerda + direita)/2;
	
		if (array[centro] < array[esquerda]){
			array = swap(array, centro, esquerda);
		}
		if (array[direita] < array[esquerda]){
			array = swap(array, direita, esquerda);
		}
		if (array[direita] < array[centro]){
			array = swap(array, direita, centro);
		}
		
		swap(array, centro, direita-1);
	}
	
	// QUICKSORT MEDIANA3
	public int[] quickSortMediana3(int[] array, int comecoDoArray, int fimDoArray){
		
		if (comecoDoArray >= fimDoArray){
			return array;
		}
		
		calculoDaMediana3(array, comecoDoArray, fimDoArray);
		
		
		int esquerda = comecoDoArray + 1;
		int direita = fimDoArray - 2;
		int p = array[fimDoArray - 1];
		
		if (esquerda > direita ){
			return array;
		}
		
		while ( true ){
			while ( array[esquerda] < p) {
				esquerda ++;
				
			}
			while ( array[direita] > p) {
				direita --;
			}
			if (esquerda < direita ){
				array = swap(array, esquerda, direita);
			} else {
				break;
			}
			
		}
		
		array = swap(array, fimDoArray - 1, esquerda);
		
		quickSortMediana3(array, comecoDoArray, esquerda - 1);
		quickSortMediana3(array, esquerda + 1, fimDoArray);
		
		return array;
	} 
	
}